import hashlib

md5_new = hashlib.md5

class ConsistentHash:
	def __init__(self, nodes, fake_node = 3):
		self._sort_nodes = []
		self._key_ring = {}
		self.fake_node = fake_node
		for i in nodes:
			self.add_node(i)
	def add_node(self,node):
		for i in xrange(0, self.fake_node):
			key = self.gen_key('%s:%s' % (node, i))
			self._key_ring[key] = node
			self._sort_nodes.append(key)
		self._sort_nodes.sort()
	def get_node(self,key):
		return self.get_node_pos(key)[0]
	def get_node_pos(self,key):
		if not self._key_ring:
			return None, None
		key = self.gen_key(key)
		nodes = self._sort_nodes
		for i in xrange(0,len(nodes)):
			node = nodes[i]
			if key <= node:
				return self._key_ring[node], i
		return self._key_ring[nodes[0]],0
	def gen_key(self,key):
		m = md5_new(key)
		return long(m.hexdigest(),16)
class ServerTable:
	def __init__(self):
		self.nodes = []
	def add(self, addr):
		self.nodes.append(addr)
	def remove(self,addr):
		self.nodes.remove(addr)
	def get(self,key):
		m = md5_new()
		hash_value = long(m.hexdigest(),16)
		return self.nodes[hash_value % len(self.nodes)]

if __name__ == '__main__':
	srv = ['127.0.0.1','127.0.0.2','127.0.0.3']
	hash_table  = ConsistentHash(srv)
	for i in xrange(10):
		print hash_table.get_node(str(i))
	hash_table.add_node('127.0.0.4')
	print '\n'
	for i in xrange(20):
		print hash_table.get_node(str(i))
